/*
 * Example_04.cpp
 *
 */

#include <iostream>
#include <iomanip>
using namespace std;

template<typename E> class Node {
private:
	E _element; // <, <=, ==, >=, >, =
	Node<E> *_parent;
	Node<E> *_left;
	Node<E> *_right;
public:
	Node( Node<E> *parent = 0) : _parent(parent), _left(0), _right(0) {}
	const E &getElement() const { return _element; }
	Node<E> *getLeft() { return _left; }
	Node<E> *getRight() { return _right; }
	Node<E> *getParent() { return _parent; }
	void setElement( const E &element ) { _element = element; }
	void setLeft( Node<E> *left ) { _left = left; }
	void setRight( Node<E> *right ) { _right = right; }
};

template<typename E> bool operator< ( const Node<E> &first, const Node<E> &second ) {
	return first.getElement() < second.getElement();
}

template<typename E> bool operator<= ( const Node<E> &first, const Node<E> &second ) {
	return first.getElement() <= second.getElement();
}

template<typename E> bool checkSubtree( Node<E> *node ) {
	// check left & right subtrees
	Node<E> *left = node->getLeft();
	if( left && ! checkLeftSubtree( node, left ) )
		return false;
	Node<E> *right = node->getRight();
	if( right && ! checkRightSubtree( node, right ) )
		return false;
	return true;
}

template<typename E> bool checkLeftSubtree( Node<E> *root, Node<E> *child ) {
	// all left subtree nodes should be < root
	if( *root <= *child ) // child should be < root
		return false;
	// left should be < child
	Node<E> *left = child->getLeft();
	if( left && *child <= *left )
		return false;
	// right should be < root and > child
	Node<E> *right = child->getRight();
	if( right && (*root <= *right || *right <= *child) )
		return false;
	// check subtree, starting from child
	return checkSubtree( child );
}

template<typename E> bool checkRightSubtree( Node<E> *root, Node<E> *child ) {
	// all right subtree nodes should be > root
	if( *child <= *root ) // child should be > root
		return false;
	// left should be > root and < child
	Node<E> *left = child->getLeft();
	if( left && (*left <= *root || *child <= *left) )
		return false;
	// right should be > child
	Node<E> *right = child->getRight();
	if( right && *right <= *child )
		return false;
	// check subtree, starting from child
	return checkSubtree( child );
}

template<typename E> class BTree {
private:
	Node<E> *_root;
	int _counter;
public:
	BTree( Node<E> *root ) : _root(root), _counter(1) {}
	void addLeft( Node<E> *node );
	void addRight( Node<E> *node );
	int const getSize() { return _counter; }
	bool const check();
};

template<typename E> void BTree<E>::addLeft( Node<E> *node ) {
	node->getParent()->setLeft( node );
	_counter++;
};

template<typename E> void BTree<E>::addRight( Node<E> *node ) {
	node->getParent()->setRight( node );
	_counter++;
}

template<typename E> bool const BTree<E>::check() {
	return checkSubtree<E>( _root );
}

//int main() {
//	Node<int> root;
//	root.setElement( 10 );
//	Node<int> l1( &root );
//	l1.setElement( 5 );
//	Node<int> r1( &root );
//	r1.setElement( 15 );
//	Node<int> l2_l1 ( &l1 );
//	l2_l1.setElement( 4 );
//	Node<int> r2_l1 ( &l1 );
//	r2_l1.setElement( 11 );
//
//	BTree<int> bTree( &root );
//	bTree.addLeft( &l1 );
//	bTree.addRight( &r1 );
//	bTree.addLeft( &l2_l1 );
//	bTree.addRight( &r2_l1 );
//
//	cout << "BTree: size=" << bTree.getSize() << "; check=" << boolalpha << bTree.check() << endl;
//}
